#ifndef RSIM_LIST_H
#define RSIM_LIST_H

/* -------------------------------------------------------------------------- *
 * File: List.h								      *
 * Authors: Kishor Bhalerao                                                   *
 * Email : kishor8dm@gmail.com                                                *
 * Contributors:                      					      *
 * Email: 								      *
 * copyright (c) 2010 Authors.                                                *
 *                                                                            *
 * This program is free software: you can redistribute it and/or modify it    *
 * under the terms of the GNU General Public License as published by the Free *
 * Software Foundation, either version 3 of the License, or any later version.*
 *									      *
 * This program is distributed in the hope that it will be useful, but        *
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY *
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License   *
 * for more details. (http://www.gnu.org/licenses/)			      *
 * -------------------------------------------------------------------------- */

#include <iostream>
#include <cstdlib>
#include <assert.h>

namespace RSIM{
	
template <class T> class List;

template <class T>
class Node{
	public:
		/** Stored data in this node */
		T *data_;
		
		/** Parent of this node. */
		Node <T>* Parent_;
		
		/** Child of this node */
		Node <T>* Child_;
		
		/** Default constructor creates a NULL node.*/
		Node():data_(NULL),Parent_(NULL),Child_(NULL){}	
		
		/** Just copies the data. This creates a stand alone node
		and can be used as a storage class for anything. */
		Node(const T &Var){
			data_ = new T; 
			*data_=Var; 
			Parent_=NULL; 
			Child_=NULL;
		}
		
		/** To be implemented. */
		void operator=(const Node<T>& Nd);
		
		/** To be implemented. */
		Node<T>(const Node<T>&);
		
		/** clear allocated space*/
		~Node(){
			delete data_;
		}
		
		/** Sets the node to Null node */
		void clear(){
			if(data_!=NULL){
				delete data_; 
				data_ = NULL; 
			}
		}
};

/**
Templatized linked list. The indexing is 0 based. List creates its own copy. 
Modifying the original would not modify the data stored in the List.
*/

template <class T>
class List{
	private:
		/** Root or the first element of the list */
		Node <T>* Root_;
		
		/** Leaf or the last element of the list */
		Node <T>* Leaf_;
		
		/** Number of elements in the list */
		int nNodes_;
		
		/** True if nNodes_=0 */
		bool isEmpty_;
		
		Node <T> **Nd_;
	public:
		/** Empty list */
		List():Root_(NULL),Leaf_(NULL),nNodes_(0),isEmpty_(true),Nd_(NULL){}
		
		/** 
		Deep copy. A copy constructor must be defined for the class T 
		*/
		List<T>(const List <T> &); 
		
		/** 
		Deep copy. 
		A copy constructor must be defined for the class T  
		*/
 		void operator=(const List <T>&);
		
		/** Delete all allocated space */
		~List(){
			this->clear();		
		}
		
		/** Add node at the end of the list (to current Leaf_ node) */
		void addNode(const T& Var);
		
		/** Add node at the beginning of the list (before current Root_ node) */
		void prepend(const T& Var);
		
		/** Deletes the root element. Length of the List decreased by 1 */
		void deleteRoot();
				
		/** Delete the allocated space */
		void clear();
		
		/** This initializes iterator Nd_ */
		void finalize();
		
		/** Delete Node specified by NodeId
		To be implemented. */
		void deleteNode(const int& NodeId);		

		/** Return total nodes */
		int getLength() const{
			return nNodes_;
		}			
		
		/** Return total nodes */
		int getnNodes() const{
			return nNodes_;
		}
		
		/** Query State of List */
		bool isListEmpty() const{
			return isEmpty_;
		}
		
		/** @return Root */
		const Node <T>* getRoot() const{
			return Root_;
		}		
		
		/** @return  Leaf */
		const Node <T>* getLeaf() const{
			return Leaf_;
		}
		
		Node <T>* getIterator()const{
			return Nd_;
		}
		
		/** Print list information starting from specified node
		A function void PrintInfo(void) must exist in the class 
		T, which is called at each time step */
		void printListInfo(const Node <T>* Nd);				
		
		/** Indexing starts from 0. 0th element is the Root. Returns a writable
		reference to the data at specified index */
		T& operator()(const int& index);
		
		/** Indexing starts from 0. 0th element is the Root. Returns a writable
		reference to the data at specified index */
		T& operator[](const int& index);
		
		/** Indexing starts from 0. 0th element is the Root. Returns a writable
		reference to the data at specified index */
		const T& operator()(const int& index)const;
		
		/** Indexing starts from 0. 0th element is the Root. Returns a writable
		reference to the data at specified index */
		const T& operator[](const int& index)const;
		
		/** Returns a constant reference to the data at specified index.
		If the function void finalize() was called, this uses the iterator.
		Otherwise, this is an O(index) operation to get to the specified index. */
		const T& getNode(const int& index) const;
                
                /** Same as getNode(const int&) */
                const T& getElement(const int& index)const;
                
                /** If the given element is found in the list, the function returns the index
                of the element in the list. If not found, the function returns -1.*/
                int findElement(const T& element)const;
		
};

///////////////////////////////////////////////////////
//         List Functions
///////////////////////////////////////////////////////

template <class T>
int List<T>::findElement(const T& Element)const{                
        for(int i=0;i<nNodes_;++i){
                if(this->getNode(i)==Element)                        
                        return i;
        }
        return -1;
}
        
///////////////////////////////////////////////////////

template <class T>
void List<T>::operator=(const List<T>& L){
	this->clear();
	for(int i=0;i<L.getLength();++i)
		this->addNode(L.getNode(i));
}

///////////////////////////////////////////////////////

template <class T>
List<T>::List(const List<T>& L){
	Root_ = NULL;
	Leaf_ = NULL;
	nNodes_ = 0;
	isEmpty_ = true;
	Nd_ = NULL;
	for(int i=0;i<L.getLength();++i)
		this->addNode(L.getNode(i));
}

///////////////////////////////////////////////////////

template <class T>
void List<T>::finalize(){
	if(nNodes_){
		Nd_ = new Node <T>*[nNodes_];
		Node <T>* tmp = Root_;
		for(int i=0;i<nNodes_;++i){
			Nd_[i]=tmp;
			tmp = tmp->Child_;
		}
	}
	else
		Nd_ = NULL;
}

///////////////////////////////////////////////////////

template <class T>
void List<T>::addNode(const T& Var){
	++nNodes_;
	isEmpty_ = false;
	if (Root_==NULL){
		Root_ = new Node <T> (Var);
		Leaf_ = Root_;
	}
	else{
		Node <T>* tmp = Leaf_;
		Leaf_ = new Node <T> (Var);
		Leaf_->Parent_ = tmp;
		tmp->Child_ = Leaf_;
	}
	if(Nd_){
		delete [] Nd_;
		Nd_ = NULL;
	}
}

///////////////////////////////////////////////////////

template <class T>
void List<T>::deleteRoot(){
	if(nNodes_==0){
		std::cout<<"\nList::deleteRoot(). Nothing to delete";
	}
	else{
		Node <T>* tmp = Root_->Child_;		
		delete Root_;
		Root_ = tmp;			
		--nNodes_;
		
	}
	if(Nd_){
		delete [] Nd_;
		Nd_ = NULL;
	}
}

///////////////////////////////////////////////////////

template <class T>
void List<T>::clear(){
	delete [] Nd_;
	Nd_ = NULL;
	
	while(nNodes_)
		deleteRoot();	
}

///////////////////////////////////////////////////////

template <class T>
void List<T>::prepend(const T& Var){
	nNodes_++;
	if (Root_==NULL){
		Root_ = new Node <T> (Var);
		Leaf_ = Root_;
	}
	else{
		Node <T>* tmp = Root_;
		Root_ = new Node <T> (Var);
		Root_->Child_ = tmp;
		tmp->Parent_ = Root_;
	}
	if(Nd_){
		delete [] Nd_;
		Nd_ = NULL;
	}
}

///////////////////////////////////////////////////////

template <class T>
inline T& List<T>::operator()(const int &index){
	if(Nd_){
		#ifdef RSIM_SAFE
			assert(index>=0);
			assert(index<nNodes_);
		#endif
		return *(Nd_[index][0].data_);		
	}
	else{
		Node <T>* tmp = Root_;
		for(int i=0;i<index;i++){
			tmp = tmp->Child_;
			if (tmp == NULL){
				std::cout<<"List.h: Index out of bounds. Exiting\n";
				exit(0);
			}
		}
		if(tmp==NULL){
			std::cout<<"List.h: List is empty. Exiting\n";
			exit(0);
		}
		return *((*tmp).data_);	
	}
}

///////////////////////////////////////////////////////

template <class T>
inline const T& List<T>::getElement(const int& index)const{
        if(Nd_){
                #ifdef RSIM_SAFE
                assert(index>=0);
                assert(index<nNodes_);
                #endif
                return *(Nd_[index][0].data_);          
        }
        else{
                Node <T>* tmp = Root_;
                for(int i=0;i<index;i++){
                        tmp = tmp->Child_;
                        if (tmp == NULL){
                                std::cout<<"List.h: Index out of bounds. Exiting\n";
                                exit(0);
                        }
                }
                if(tmp==NULL||index<0){
                        std::cout<<"List.h: List is empty or attempt to access ground. Exiting\n";
                        exit(0);
                }
                return  *((*tmp).data_);
        }
}

template <class T>
inline const T& List<T>::getNode(const int &index) const {
	if(Nd_){
		#ifdef RSIM_SAFE
			assert(index>=0);
			assert(index<nNodes_);
		#endif
		return *(Nd_[index][0].data_);		
	}
	else{
		Node <T>* tmp = Root_;
		for(int i=0;i<index;i++){
			tmp = tmp->Child_;
			if (tmp == NULL){
				std::cout<<"List.h: Index out of bounds. Exiting\n";
				exit(0);
			}
		}
		if(tmp==NULL||index<0){
			std::cout<<"List.h: List is empty or attempt to access ground. Exiting\n";
			exit(0);
		}
		return  *((*tmp).data_);
	}
}

///////////////////////////////////////////////////////

template <class T>
inline T& List<T>::operator[](const int &index){
	if(Nd_){
		#ifdef RSIM_SAFE
			assert(index>=0);
			assert(index<nNodes_);
		#endif
		return *(Nd_[index][0].data_);		
	}
	else{
		Node <T>* tmp = Root_;
		for(int i=0;i<index;i++){
			tmp = tmp->Child_;
			if (tmp == NULL){
				std::cout<<"List.h: Index out of bounds. Exiting\n";
				exit(0);
			}
		}
		if(tmp==NULL){
			std::cout<<"List.h: List is empty, or attempt to access root. Exiting\n";
			exit(0);
		}
		return *((*tmp).data_);	
	}
}

///////////////////////////////////////////////////////

template <class T>
inline const T& List<T>::operator[](const int &index)const{
	if(Nd_){
		#ifdef RSIM_SAFE
                if(index<0 || index>=nNodes_){
                        std::cout<<"List.h: Index out of bounds. Correct value should be between 0 and "<< nNodes_-1<<std::endl<<
                        "Input value is "<<index<<"\n\n";
                        assert(0);
                }       
		#endif
		return *(Nd_[index][0].data_);		
	}
	else{
		Node <T>* tmp = Root_;
		for(int i=0;i<index;i++){
			tmp = tmp->Child_;
			if (tmp == NULL){
				std::cout<<"List.h: Index out of bounds. Exiting\n";
				exit(0);
			}
		}
		if(tmp==NULL){
			std::cout<<"List.h: List is empty, or attempt to access root. Exiting\n";
			exit(0);
		}
		return *((*tmp).data_);	
	}
}

///////////////////////////////////////////////////////

template <class T>
inline const T& List<T>::operator()(const int &index)const{
	if(Nd_){
		#ifdef RSIM_SAFE
			assert(index>=0);
			assert(index<nNodes_);
		#endif
		return *(Nd_[index][0].data_);		
	}
	else{
		Node <T>* tmp = Root_;
		for(int i=0;i<index;i++){
			tmp = tmp->Child_;
			if (tmp == NULL){
				std::cout<<"List.h: Index out of bounds. Exiting\n";
				exit(0);
			}
		}
		if(tmp==NULL){
			std::cout<<"List.h: List is empty, or attempt to access root. Exiting\n";
			exit(0);
		}
		return *((*tmp).data_);	
	}
}

///////////////////////////////////////////////////////

template <class T>
void List<T>::printListInfo(const Node <T>* Nd){
	if(Nd != NULL){
		(Nd->data_)->printInfo();
		printListInfo(Nd->Child_);
	}
}

///////////////////////////////////////////////////////

} // namespace RSIM

#endif